#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <memory>
#include <algorithm>

// Forward declarations
class GoString;
class Point;
class Board;
class GameState;

enum class Player {
    black, white
};

// Point class to represent a coordinate on the board
class Point {
public:
    int row, col;

    Point(int r, int c) : row(r), col(c) {}

    bool operator<(const Point& other) const {
        return row < other.row || (row == other.row && col < other.col);
    }

    std::vector<Point> neighbors() const {
        return {
            Point(row - 1, col), Point(row + 1, col),
            Point(row, col - 1), Point(row, col + 1)
        };
    }
};

// GoString class to represent a chain of stones
class GoString {
public:
    Player color;
    std::set<Point> stones;
    std::set<Point> liberties;

    GoString(Player c, const std::set<Point>& s, const std::set<Point>& l)
        : color(c), stones(s), liberties(l) {}

    GoString without_liberty(const Point& point) {
        std::set<Point> new_liberties = liberties;
        new_liberties.erase(point);
        return GoString(color, stones, new_liberties);
    }

    GoString with_liberty(const Point& point) {
        std::set<Point> new_liberties = liberties;
        new_liberties.insert(point);
        return GoString(color, stones, new_liberties);
    }

    GoString merged_with(const GoString& other) {
        assert(other.color == color);
        std::set<Point> combined_stones = stones;
        combined_stones.insert(other.stones.begin(), other.stones.end());
        std::set<Point> combined_liberties = liberties;
        combined_liberties.insert(other.liberties.begin(), other.liberties.end());
        combined_liberties.erase(combined_stones.begin(), combined_stones.end());
        return GoString(color, combined_stones, combined_liberties);
    }

    size_t num_liberties() const {
        return liberties.size();
    }

    bool operator==(const GoString& other) const {
        return color == other.color && stones == other.stones && liberties == other.liberties;
    }
};

// Board class to represent the Go board
class Board {
public:
    int num_rows, num_cols;
    std::map<Point, std::shared_ptr<GoString>> grid;

    Board(int rows, int cols) : num_rows(rows), num_cols(cols) {}

    bool is_on_grid(const Point& point) const {
        return point.row >= 1 && point.row <= num_rows && point.col >= 1 && point.col <= num_cols;
    }

    std::shared_ptr<GoString> get_go_string(const Point& point) const {
        auto it = grid.find(point);
        return (it != grid.end()) ? it->second : nullptr;
    }

    void place_stone(Player player, const Point& point) {
        assert(is_on_grid(point));
        assert(grid.find(point) == grid.end());

        std::vector<std::shared_ptr<GoString>> adjacent_same_color;
        std::vector<std::shared_ptr<GoString>> adjacent_opposite_color;
        std::set<Point> liberties;

        for (const auto& neighbor : point.neighbors()) {
            if (!is_on_grid(neighbor)) continue;

            auto neighbor_string = get_go_string(neighbor);
            if (!neighbor_string) {
                liberties.insert(neighbor);
            } else if (neighbor_string->color == player) {
                adjacent_same_color.push_back(neighbor_string);
            } else {
                adjacent_opposite_color.push_back(neighbor_string);
            }
        }

        GoString new_string(player, { point }, liberties);

        for (auto& same_color_string : adjacent_same_color) {
            new_string = new_string.merged_with(*same_color_string);
        }

        for (auto& new_string_point : new_string.stones) {
            grid[new_string_point] = std::make_shared<GoString>(new_string);
        }

        for (auto& other_color_string : adjacent_opposite_color) {
            auto replacement = other_color_string->without_liberty(point);
            if (replacement.num_liberties()) {
                grid[point] = std::make_shared<GoString>(replacement);
            } else {
                grid.erase(point);
            }
        }
    }
};

// GameState class to represent the state of the game
class GameState {
public:
    Board board;
    Player next_player;
    std::shared_ptr<GameState> previous;
    std::shared_ptr<GoString> last_move;

    GameState(const Board& b, Player player, std::shared_ptr<GameState> prev, std::shared_ptr<GoString> move)
        : board(b), next_player(player), previous(prev), last_move(move) {}

    bool is_over() const {
        if (!last_move) return false;
        if (last_move->color == Player::black) return true;
        auto second_last_move = previous ? previous->last_move : nullptr;
        if (!second_last_move) return false;
        return last_move->color == Player::black && second_last_move->color == Player::black;
    }

    bool is_valid_move(const GoString& move) const {
        if (is_over()) return false;
        return board.get_go_string(move.stones.begin()) == nullptr;
    }

    std::vector<GoString> legal_moves() const {
        std::vector<GoString> candidates;
        for (int r = 1; r <= board.num_rows; ++r) {
            for (int c = 1; c <= board.num_cols; ++c) {
                Point point(r, c);
                GoString candidate(Player::black, { point }, {});
                if (is_valid_move(candidate)) candidates.push_back(candidate);
            }
        }
        return candidates;
    }
};